package com.yanceysong.codetop.s61_s70;

import com.yanceysong.common.TreeNode;

import java.util.*;

public class S65_Easy_101_对称二叉树 {
    /**
     * S65_Easy_101_对称二叉树
     * <p>
     * <a href="https://leetcode.cn/problems/symmetric-tree/">题目链接</a>
     * <p>
     * 题目描述：
     * 给定一个二叉树的根节点 root ，判断它是否是轴对称（关于根节点的垂直轴镜像）。
     * "轴对称"含义：一棵树的左子树与右子树结构完全镜像且对应节点值相等。
     * <p>
     * 例子：
     * 1. 对称：
     *            1
     *          /   \
     *         2     2
     *        / \   / \
     *       3  4  4   3
     * 2. 不对称（结构破坏）：
     *            1
     *          /   \
     *         2     2
     *          \     \
     *          3      3
     * 3. 不对称（值破坏）：
     *            1
     *          /   \
     *         2     2
     *        /       \
     *       3         4
     * <p>
     * 判定标准：对于一对要比较的节点 (L, R)：
     * 1) 二者都为空 -> 对称
     * 2) 仅一者为空 -> 不对称
     * 3) 值不同 -> 不对称
     * 4) 继续比较：L.left vs R.right 与 L.right vs R.left
     * <p>
     * 递归算法（深度优先）：
     * 核心函数 isMirror(l, r) ：判断以 l 和 r 为根的两棵子树是否镜像。
     * 终止条件覆盖全部结构差异；递归向下扩展内外侧配对。
     * <p>
     * 迭代算法（广度优先）：
     * 使用队列成对存储节点，弹出两个进行相同规则比较，并按镜像顺序入队：
     *  (l.left, r.right) 以及 (l.right, r.left)
     * <p>
     * ASCII 镜像对比（外侧与内侧同时匹配）：
     * 左子树               右子树
     *     2                   2
     *   /   \               /   \
     *  3     4             4     3
     * 外侧: 3 ↔ 3   内侧: 4 ↔ 4     → 全部匹配 → 镜像成立
     * <p>
     * 常见误区：
     * 1) 只比较值不比较结构（会把 [1,2] 与 [1,null,2] 误判为对称）
     * 2) 入队/递归时配对顺序错误（应是左的左 vs 右的右，左的右 vs 右的左）
     * 3) 忽略空树情况（空树天然对称）
     * <p>
     * 复杂度分析：
     * 时间：O(n) — 每个节点访问一次
     * 空间：递归 O(h)（最坏退化链 O(n)，平均平衡 O(log n)）；迭代队列最坏一层 O(w)
     * <p>
     * 边界测试建议：
     * - 空树
     * - 单节点
     * - 完全对称与一处破坏结构 / 数值
     * - 深层嵌套含 null 间隙
     * - 仅最底层一个叶子不匹配
     * <p>
     * @param root 根节点
     * @return 是否为对称二叉树
     */
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }

    /**
     * 判断两个节点为根的子树是否镜像。
     * 递归结构：当前节点值相等 且 外侧子树镜像 且 内侧子树镜像。
     * 终止条件：
     *  - 均为空 => true
     *  - 仅一空 => false
     */
    private boolean isMirror(TreeNode leftSubtreeRoot, TreeNode rightSubtreeRoot) {
        if (leftSubtreeRoot == null && rightSubtreeRoot == null) {
            return true;
        }
        if (leftSubtreeRoot == null || rightSubtreeRoot == null) {
            return false;
        }
        // 当前值相等 + 外侧镜像 + 内侧镜像
        return leftSubtreeRoot.val == rightSubtreeRoot.val
                && isMirror(leftSubtreeRoot.left, rightSubtreeRoot.right)
                && isMirror(leftSubtreeRoot.right, rightSubtreeRoot.left);
    }

    /**
     * 迭代版本：利用队列做成对弹出与成对入队（宽度遍历的镜像配对）。
     * 队列中始终保持镜像对应的两个节点紧挨顺序入队：外侧 + 内侧。
     */
    public boolean isSymmetricIterative(TreeNode root) {
        if (root == null) {
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode leftNode = queue.poll();
            TreeNode rightNode = queue.poll();
            if (leftNode == null && rightNode == null) {
                continue; // 成对为空，跳过
            }
            if (leftNode == null || rightNode == null) {
                return false; // 结构不匹配
            }
            if (leftNode.val != rightNode.val) {
                return false; // 数值不匹配
            }
            // 镜像顺序入队：外侧(left.left, right.right) + 内侧(left.right, right.left)
            queue.offer(leftNode.left);
            queue.offer(rightNode.right);
            queue.offer(leftNode.right);
            queue.offer(rightNode.left);
        }
        return true;
    }

    // ================= 工具 & 构造辅助 =================

    /**
     * 根据层序数组构建二叉树（null 表示缺失）。
     * 示例：[1,2,2,3,4,4,3] => 完全对称。
     */
    public static TreeNode buildTree(Integer[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(values[0]);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int idx = 1;
        while (!queue.isEmpty() && idx < values.length) {
            TreeNode current = queue.poll();
            // 左孩子
            if (idx < values.length) {
                Integer leftVal = values[idx++];
                if (leftVal != null) {
                    current.left = new TreeNode(leftVal);
                    queue.offer(current.left);
                }
            }
            // 右孩子
            if (idx < values.length) {
                Integer rightVal = values[idx++];
                if (rightVal != null) {
                    current.right = new TreeNode(rightVal);
                    queue.offer(current.right);
                }
            }
        }
        return root;
    }

    /**
     * 返回裁剪后的层序打印（仅展开存在子节点的层，避免冗长尾部 null）。
     */
    public static String levelOrder(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        List<String> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            if (node == null) {
                list.add("null");
            } else {
                list.add(String.valueOf(node.val));
                if (node.left != null || node.right != null) {
                    q.offer(node.left);
                    q.offer(node.right);
                }
            }
        }
        return list.toString();
    }

    // ================== 测试用例 ==================

    public static void main(String[] args) {
        S65_Easy_101_对称二叉树 solution = new S65_Easy_101_对称二叉树();
        System.out.println("=== 对称二叉树测试开始 ===\n");

        // 1. 空树
        System.out.println("[测试1] 空树 => true");
        testAndAssert(solution, null, true);

        // 2. 单节点
        System.out.println("\n[测试2] 单节点 => true");
        testAndAssert(solution, new TreeNode(1), true);

        // 3. 完全对称示例
        System.out.println("\n[测试3] 完全对称 [1,2,2,3,4,4,3] => true");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, 3, 4, 4, 3}), true);

        // 4. 结构不对称
        System.out.println("\n[测试4] 结构不对称 [1,2,2,null,3,null,3] => false");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, null, 3, null, 3}), false);

        // 5. 两层对称
        System.out.println("\n[测试5] 两层对称 [1,2,2] => true");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2}), true);

        // 6. 两层值不对称
        System.out.println("\n[测试6] 两层值不对称 [1,2,3] => false");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 3}), false);

        // 7. 深度对称含空缺
        System.out.println("\n[测试7] 深度对称含空缺 [1,2,2,3,null,null,3,4,null,null,4] => true");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, 3, null, null, 3, 4, null, null, 4}), true);

        // 8. 细微不对称（缺少叶子）
        System.out.println("\n[测试8] 细微不对称 [1,2,2,3,null,null,3,4,null,null,null] => false");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, 3, null, null, 3, 4, null, null, null}), false);

        // 9. 底层值不等
        System.out.println("\n[测试9] 底层值不等 [1,2,2,3,4,4,5] => false");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, 3, 4, 4, 5}), false);

        // 10. 非完全但仍对称 (带内部 null) [1,2,2,null,3,3,null]
        System.out.println("\n[测试10] 非完全但对称 [1,2,2,null,3,3,null] => true");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, null, 3, 3, null}), true);

        // 11. 单侧延伸不对称 [1,2,2,3,null,null,null]
        System.out.println("\n[测试11] 单侧延伸不对称 [1,2,2,3,null,null,null] => false");
        testAndAssert(solution, buildTree(new Integer[]{1, 2, 2, 3, null, null, null}), false);

        // 12. 随机一致性校验（递归 vs 迭代）
        System.out.println("\n[测试12] 随机一致性校验");
        Random random = new Random(42);
        for (int round = 1; round <= 5; round++) {
            Integer[] arr = randomSymmetricCandidate(random, 9);
            TreeNode tree = buildTree(arr);
            boolean r1 = solution.isSymmetric(tree);
            boolean r2 = solution.isSymmetricIterative(tree);
            System.out.printf("Round %d: %s -> 递归:%s / 迭代:%s%n", round, Arrays.toString(arr), r1, r2);
            assert r1 == r2 : "递归与迭代结果不一致";
        }

        System.out.println("\n=== 所有测试结束 ===");
    }

    /**
     * 构造一个可能对称的层序数组，随机插入 null 与扰动值。
     */
    private static Integer[] randomSymmetricCandidate(Random random, int maxLen) {
        int len = 1 + random.nextInt(Math.max(1, maxLen));
        Integer[] base = new Integer[len];
        for (int i = 0; i < len; i++) {
            base[i] = (i == 0) ? random.nextInt(5) : (random.nextDouble() < 0.2 ? null : random.nextInt(5));
        }
        if (random.nextBoolean() && len > 2) {
            int pos = random.nextInt(len);
            if (base[pos] != null) {
                base[pos] = (base[pos] + 1) % 10; // 轻微扰动打破镜像
            }
        }
        return base;
    }

    /**
     * 统一执行测试与断言，打印两种算法结果。
     */
    private static void testAndAssert(S65_Easy_101_对称二叉树 solution, TreeNode root, boolean expected) {
        boolean recursiveResult = solution.isSymmetric(root);
        boolean iterativeResult = solution.isSymmetricIterative(root);
        System.out.println("层序: " + levelOrder(root));
        System.out.println("递归: " + recursiveResult + " / 迭代: " + iterativeResult + " (期望: " + expected + ")");
        assert recursiveResult == expected : "递归结果不符合期望";
        assert iterativeResult == expected : "迭代结果不符合期望";
        assert recursiveResult == iterativeResult : "两者实现结果不一致";
        System.out.println("✓ 测试通过");
    }
}
